package com.sunny;

import java.util.concurrent.ForkJoinPool;
import java.util.concurrent.RecursiveAction;

/**
 * 归并排序 fork join
 * 未百分百成功，求证原因（之前未成功，是因为打印的最终结果太早，归并排序还没结束，加上sleep后可以成功）
 */
public class SortTask extends RecursiveAction {

    private static final int THRESHOLD = 2;

    private int[] arr;
    private int start;
    private int end;

    public SortTask(int start, int end, int[] arr) {
        this.arr = arr;
        this.start = start;
        this.end = end;
    }

    @Override
    protected void compute() {
        System.out.println(start + " " + end);
        if (end - start + 1 <= THRESHOLD) {
            if (start == end) {
                return;
            } else {
                if (arr[start] > arr[end]) {
                    swap(arr, start, end);
                }
            }
        } else {
            int mid = start + ((end - start) >> 1);
            SortTask sub1 = new SortTask(start, mid, arr);
            SortTask sub2 = new SortTask(mid + 1, end, arr);
            sub1.fork();
            sub2.fork();
//            sub2.compute(); // 第二个子任务直接由当天线程来计算，节约线程
            sub1.join();
            sub2.join();

            int i = start;
            int j = mid + 1;
            int k = 0;
            int[] array = new int[end - start + 1];
            while (i <= mid && j <= end) {
                if (arr[i] <= arr[j]) {
                    array[k++] = arr[i++];
                } else {
                    array[k++] = arr[j++];
                }
            }
            while (i <= mid) {
                array[k++] = arr[i++];
            }
            while (j <= end) {
                array[k++] = arr[j++];
            }
            for (int ii = start; ii <= end; ii++) {
                arr[ii] = array[ii - start];
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {100, 8, 90, 5, 78, 3, 2, 88, 9, 67, 56, 66, 1, 36, 33, 23, 70};
        ForkJoinPool pool = new ForkJoinPool(10);
        pool.execute(new SortTask(0, 16, arr));
        try {
            Thread.sleep(3000);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        for (int i = 0; i < arr.length; i++) {
            if (i != 0) {
                System.out.print(" ");
            } else {
                System.out.println();
            }
            System.out.print(arr[i]);
        }
    }

    private void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    /**
     * 位运算
     * @param arr
     * @param i
     * @param j
     */
    private void swap1(int[] arr, int i, int j) {
        arr[i] = arr[i] ^ arr[j];
        arr[j] = arr[i] ^ arr[j];
        arr[i] = arr[i] ^ arr[j];
    }

    /**
     * 加法
     * @param arr
     * @param i
     * @param j
     */
    private void swap2(int[] arr, int i, int j) {
        arr[i] = arr[i] + arr[j];
        arr[j] = arr[i] - arr[j];
        arr[i] = arr[i] - arr[j];
    }


}
